package top.minuy.structure.tree.avl;

import top.minuy.structure.linear.array.Array;

/**
 * AVL数，平衡二叉树
 *
 * @author Minuy
 * @time 19:39
 * @date 2021/11/1
 */
public class AVLTree<E extends Comparable<E>> {
    /**
     * 二叉树节点
     */
    private class Node {
        // 元素
        public E e;
        // 左右节点
        public Node left, right;
        // 树当前的高度
        int height;

        public Node(E e) {
            this(e, null, null, 1);
        }

        public Node(E e, Node left, Node right, int height) {
            this.e = e;
            this.left = left;
            this.right = right;
            this.height = height;
        }
    }

    // 根节点
    private Node root;
    // 大小
    private int size;

    /**
     * 创建一个二分搜索树
     */
    public AVLTree() {
        root = null;
        size = 0;
    }

    /**
     * 获取树大小
     *
     * @return 树的大小
     */
    public int size() {
        return size;
    }

    /**
     * 判断树是否为空
     *
     * @return 是否为空树
     */
    public boolean isEmpty() {
        return size == 0;
    }


    /**
     * 从树中删除元素e
     *
     * @param e 被删除的元素e
     */
    public void remove(E e) {
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }

        // 方便统一一下
        Node retNode;

        if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            retNode = node;
        } else if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            retNode = node;
        } else { // e == node.e

            if (node.left == null) {
                Node t = node.right;
                node.right = null;
                size--;
                retNode = t;
                // 之前这里三个情况是return，只运行一个，所以应该使用else包围一下
            } else if (node.right == null) {
                Node t = node.left;
                node.left = null;
                size--;
                retNode = t;
            } else {

                Node successor = minimum(node.right);  // 找出后继

                // 在这里删除了结点，但是没有进行维护平衡
                // node.right = removeMin(node.right);   // 把后继脱离出当前的树(这里size已经-1了)
                node.right = remove(node.right, successor.e); // 复用本方法，可以复用后面的维护代码

                successor.right = node.right;  // 后继替代当前节点
                successor.left = node.left;  // 后继替代当前节点

                node.right = node.left = null;  // 当前节点断开连接

                retNode = successor;
            }
        }

        if (retNode == null) {
            // 如果将要被维护的结点是空的，就不需要维护了
            return null;
        }

        //维护高度
        retNode.height = 1 + (Math.max(getHeight(retNode.right), getHeight(retNode.left)));

        int balanceFactor = getBalanceFactor(retNode);
        // LL
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {// （LR）
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rightRotate(retNode.right); // 转换成RR
            return leftRotate(retNode);
        }

        return retNode;
    }

    /**
     * 获取结点中的最小值
     *
     * @param node 结点
     * @return 最小的节点
     */
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    private int getHeight(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    /**
     * 获取所有的值
     *
     * @return Array<E> 所有的值组成的列表
     * @author Minuy
     * @date 2021/11/15 22:16
     */
    public Array<E> getArray() {
        Array<E> keys = new Array<>(size);
        inOrder(root, keys);
        return keys;
    }

    /**
     * 判断这棵树是不是二分搜索树
     *
     * @return 是/不是
     */
    public boolean isBST() {
        Array<E> keys = new Array<>(size);
        inOrder(root, keys);
        for (int i = 1; i < keys.getSize(); i++) {
            if (keys.get(i - 1).compareTo(keys.get(i)) > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 为isBST()服务，中序遍历，放在Array中
     *
     * @param node  遍历开始的结点
     * @param array 数组
     */
    private void inOrder(Node node, Array<E> array) {
        if (node == null) {
            return;
        }
        inOrder(node.left, array);
        array.addLast(node.e);
        inOrder(node.right, array);
    }

    /**
     * 判断一棵树是不是平衡二叉树
     *
     * @return 是/不是
     */
    public boolean isBalanced() {
        return isBalanced(root);
    }

    /**
     * 判断是否是平衡二叉树，递归
     *
     * @param node 判断的树的根
     * @return 是/不是
     */
    private boolean isBalanced(Node node) {
        if (node == null) {
            return true;
        }
        // 如果平衡因子的绝对值大于1，则不是平衡二叉树
        if (Math.abs(getBalanceFactor(node)) > 1) {
            return false;
        }
        return isBalanced(node.right) && isBalanced(node.left);
    }

    /**
     * 计算当前节点的平衡因子
     *
     * @param node 要计算的节点
     * @return 平衡因子（左右子树高度差）
     */
    private int getBalanceFactor(Node node) {
        if (node == null) {
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    /**
     * 向AVL树中添加元素
     *
     * @param e 要被添加的元素
     */
    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 对结点y进行右旋转操作，返回旋转后新的根节点x
     * .        y                       x
     * .       / \                    /   \
     * .      x  T4   向右旋转（y）    z     y
     * .     / \      --------->   / \    / \
     * .    z  T3                T1  T2  T3 T4
     * .   / \
     * . T1  T2
     *
     * @return 旋转后的根节点 x
     */
    private Node rightRotate(Node y) {
        Node x = y.left;
        Node T3 = x.right;

        x.right = y;
        y.left = T3;

        // 更新高度，不要忘记加一
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        return x;
    }

    /**
     * 对结点y进行左旋转操作，返回旋转后新的根节点x
     * .   y                          x
     * .  / \                       /   \
     * . T1  x      向左旋转（y）    y     z
     * .    / \     --------->   / \    / \
     * .  T2   z               T1  T2  T3 T4
     * .      / \
     * .    T3  T4
     *
     * @return 旋转后的根节点 x
     */
    private Node leftRotate(Node y) {
        Node x = y.right;
        Node T2 = x.left;

        x.left = y;
        y.right = T2;

        // 更新高度，不要忘记加一
        y.height = 1 + Math.max(getHeight(y.left), getHeight(y.right));
        x.height = 1 + Math.max(getHeight(x.left), getHeight(x.right));
        return x;
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        } else if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        }

        // ++++++++AVL计算当前节点高度+++++++++++
        node.height = 1 + (Math.max(getHeight(node.right), getHeight(node.left)));
        // System.out.println(node.e+"高度："+node.height);

        int balanceFactor = getBalanceFactor(node);

        // getBalanceFactor(node.left)>=0
        // 是对                      y
        // .     x(3,2)            / \
        // .    /                 x  T6
        // .   y(2,1)           /     \
        // .    \              z      T3
        // .     z(1,0)       / \    / \
        // .                T1  T2  T4 T5
        // 这种情况的不适用，右高于左同理。第二种情况也同样适用（getBalanceFactor(node.left)==0）

        // LL
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {// 左侧的左侧 （LL）
            return rightRotate(node);
//            // 左高于右，右旋转
//            Node r = node.left; // 左节点作为根
//            node.left = r.right; // 根的右节点插入到node的左节点中
//            r.right = node;
//            // 更新高度，不要忘记加一
//            node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
//            r.height = 1+Math.max(getHeight(r.left),getHeight(r.right));
//            return r;
        }

        // LR
        if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {// （LR）
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RR
        if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {// 右侧的右侧（RR）
            return leftRotate(node);
//            // 右高于左，左旋转
//            Node r = node.right;
//            node.right = r.left;
//            r.left = node;
//            // 更新高度，不要忘记加一
//            node.height = 1+Math.max(getHeight(node.left),getHeight(node.right));
//            r.height = 1+Math.max(getHeight(r.left),getHeight(r.right));
//            return r;
        }

        // RL
        if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { // （RL）
            node.right = rightRotate(node.right); // 转换成RR
            return leftRotate(node);
        }

        // 满足有返回值语法
        return node;
    }

    /**
     * 添加结点的非递归实现
     *
     * @param e 要添加的元素
     */
    /*public void addNr(E e) {

        if (root == null) {
            // 头结点这里不要忘了维护size
            size++;
            root = new Node(e);
            return;
        }
        // 如果不存在
        boolean notContains = !contains(e);

        Node tagNode = root;
        while (true) {
            if (e.compareTo(tagNode.e) < 0) {
                // 需要在新建结点之前，否则最后一个更新不上去
                if (notContains) {
                    tagNode.height++;
                    // System.out.println(tagNode.e + "非递归实现，高度：" + tagNode.height);
                }

                // 到左节点去
                if (tagNode.left == null) {
                    tagNode.left = new Node(e);
                    size++;
                    return;
                }
                tagNode = tagNode.left;
            } else if (e.compareTo(tagNode.e) > 0) {
                // 需要在新建结点之前，否则最后一个更新不上去
                if (notContains) {
                    tagNode.height++;
                    // System.out.println(tagNode.e + "非递归实现，高度：" + tagNode.height);
                }

                // 到右节点去
                if (tagNode.right == null) {
                    tagNode.right = new Node(e);
                    size++;
                    return;
                }
                tagNode = tagNode.right;
            } else {
                // 遇到相等的，直接不用再添加了
                return;
            }
        }
    }*/

    /**
     * 查找元素是否存在二分搜索树中
     *
     * @param e 要搜索的元素
     * @return 是否存在
     */
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }

        if (e.compareTo(node.e) == 0) {
            return true;
        }
        /*
        boolean left = false,right = false;
        if(node.left!=null){
             left = contains(node.left,e);
        }
        if (node.right!=null){
            right = contains(node.right,e);
        }
        return left || right;

         */
        if (e.compareTo(node.e) < 0) {
            // 小于节点，到左边去找
            return contains(node.left, e);
        } else {
            // 大于节点，到右边去找
            return contains(node.right, e);
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    /**
     * 生成二分搜索树的字符串
     *
     * @param node  二分搜索树的根节点
     * @param depth 当前深度
     * @param res   字符串构建对象
     */
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        generateDepthString(depth, res);
        if (node == null) {
            res.append("null");
            res.append("\n");
        } else {
            res.append("val = " + node.e.toString() + ",height = " + node.height);
            res.append("\n");

            generateBSTString(node.left, depth + 1, res);
            generateBSTString(node.right, depth + 1, res);
        }
    }

    /**
     * 生成树层次长度
     *
     * @param depth 层次
     * @param res   字符串构造器
     */
    private void generateDepthString(int depth, StringBuilder res) {
        for (int i = 0; i < depth; i++) {
            res.append("-|");
        }
    }
}
